Section: New Results

Algorithmes/Algorithms

Méthodes multigrilles pour le contrôle stochastique et les jeux répétés à somme nulle/Multigrid methods for stochastic control and repeated zero sum games

Participants : Marianne Akian, Sylvie Detournay.

L'algorithme d'itération sur les politiques est bien connu pour résoudre efficacement les équations de la programmation dynamique associées à des problèmes de contrôle stochastique avec critère à horizon infini (Howard) ou ergodique (Denardo et Fox). Récemment, il a été généralisé au cas de problèmes de jeux à deux joueurs et somme nulle dégénérés (avec paiements ergodiques et de type “multi-chaîne”), au moyen de techniques d'algèbre max-plus et de théorie du potentiel non linéaire  [103] . Chaque itération de base de cet algorithme utilise la résolution d'un système d'équations linéaires dont l'opérateur est monotone, mais dont la taille peut être grande, soit parce qu'il provient d'une discrétisation fine d'une équation aux dérivées partielles, soit parce qu'il est associé à un problème discret de grande taille comme le graphe du Web.

Or, la méthode multigrille est l'une des rares méthodes permettant de résoudre, au moins dans les bons cas, des systèmes linéaires en un temps de l'ordre de la taille du système. De plus, alors que la méthode multigrille classique ne s'applique qu'à des discrétisations d'équations aux dérivées partielles elliptiques, la méthode multigrille algébrique (voir par exemple  [172] ) peut s'appliquer à tout système linéaire présentant des propriétés de monotonie (principe du maximum ou système avec M-matrice).

L'association entre méthodes multigrilles et itérations sur les politiques a déjà été utilisée et étudiée dans le cas de problèmes de contrôle stochastique actualisé (voir par exemple  [72] , [80] ), ainsi que dans le cas d'un algorithme d'itération sur les politiques simplifié pour le contrôle ergodique (voir par exemple [5] ), mais pour lequel il n'existe pas de preuve de convergence. La méthode multigrille algébrique a été récemment associée à des méthodes d'apprentissage (voir par exemple  [187] ). Nous l'avons aussi testée dans le cas de l'itération sur les politiques pour des problèmes de jeux à somme nulle actualisés au cours du stage de Shantanu Gangal en 2007.

La thèse de Sylvie Detournay a pour but de développer et d'étudier un algorithme associant une méthode d'itération sur les politiques du type de celle introduite par Cochet-Terrasson et Gaubert dans  [103] et une méthode multigrille algèbrique, afin de résoudre des problèmes de jeux à somme nulle dégénérés, éventuellement posés directement sous forme discrète. Sylvie Detournay a d'abord travaillé sur le cas non dégénéré (actualisé) en codant d'abord seulement l'itération sur les politiques (en C) et appelant des codes libres de méthodes multigrilles algèbriques. Ces codes n'étant pas assez souples pour être modifiés, elle a ensuite codé elle-même certains types de méthodes multigrilles algébriques. Des tests sur des discrétisations d'équations aux dérivées partielles d'Hamilton-Jacobi-Bellman ou d'Isaacs, ou d'inéquations variationnelles ont donné de bons résultats et sont présentés dans [15] .

Sylvie Detournay a travaillé cette année sur le cas de problèmes avec critère moyen en temps. Elle a implémenté et raffiné l'algorithme proposé par Cochet-Terrasson et Gaubert  [103] , en l'associant soit à des méthodes de résolution exacte de systèmes linéaires, soit à des méthodes multigrilles algébriques, en utilisant aussi des méthodes multigrilles multiplicatives pour le calcul de la mesure invariante de chaînes de Markov irréductibles. Ceci a permis en particulier l'obtention de résultats numériques dans le cas de discrétisations d'équations d'Isaacs associées à des jeux de poursuite déterministes ou aléatoires. Plusieurs de ces résultats ont été présentés cette année lors de 2 conférences internationales [44] , [45] , et devraient faire l'objet d'un article en préparation. Par ailleurs dans un article avec Jean Cochet-Terrasson et Stéphane Gaubert [54] , nous présentons l'algorithme, sa convergence et des résultats numériques obtenus avec des méthodes de résolution exacte de systèmes linéaires.

English version

Policy iteration is a powerful and well known algorithm to solve the dynamic programming equation associated to one player problems. It has recently been extended to degenerate two players problems (with ergodic payoff and in “multichain” cases) using ideas from max-plus algebra and nonlinear potential theory  [103] . One basic iteration of the algorithm consists in solving a linear system which operator is monotone, but which size may be large since it comes from the discretization of a partial differential equation or since it is associated to a large size discrete problem such as the Web graph.

For the solution of large size linear systems, the state of art consists of multigrid methods which are often able to solve systems in linear time. Whereas multigrid methods can only be applied to systems that come from discretizations of elliptic partial differential equations, algebraic multigrid methods (see for instance  [172] ) can be applied to any linear system with monotonicity properties (discrete maximum principle or system with a M-matrix).

The association of multigrid methods with policy iteration has been used and studied in the case of discounted stochastic control problems (see for instance  [72] , [80] ), or in the case of a simplified policy iteration algorithm for ergodic control (see for instance [5] ), but for which no proof of convergence is known. Some recent work combines the algebraic multigrid method with learning methods  [187] . We have also tested it in the case of policy iterations for discounted zero-sum two-player games, during the internship of Shantanu Gangal in 2007.

The aim of the PhD thesis of Sylvie Detournay is to develop and study an algorithm for degenerate two player games (that may come from a discrete time and finite state space model) combining a policy iteration such as that introduced in  [103] and an algebraic multigrid method (AMG). Sylvie Detournay has first worked on the nondegenerate (discounted) case, by coding first the policy iterations (in C) and using free AMG softwares. Since these softwares cannot be modified easily, she has then implemented some types of AMG algorithms (in C). Some tests on discretisations of Hamilton-Jacobi-Bellman or Isaacs partial differential equations or variational inequalities gave good results and are presented in [15] .

She has worked this year on the case of problems with mean-payoff criteria. She has implemented and refined the algorithm proposed by Cochet-Terrasson and Gaubert  [103] , associated either to direct linear solvers, or to the AMG methods already used in the nondegenerate case, and also used multiplicative AMG methods developped in the literature for computing invariant measures of Markov chains. This allows her to obtain numerical results in the case of discretisations of Isaacs equations associated to deterministic or stochastic pursuit games. Several of these results were presented this year in 2 international conferences [44] , [45] and are part of an article in preparation. Moreover, in an article with Jean Cochet-Terrasson and Stéphane Gaubert [54] , we are presenting the algorithm, its convergence and numerical results obtained with direct linear solvers.

Algorithmique des polyèdres tropicaux/Algorithmics of tropical polyhedra

Participants : Xavier Allamigeon, Stéphane Gaubert, Eric Goubault [CEA] .

X. Allamigeon, S. Gaubert, et E. Goubault, ont développé dans  [82] , [57] plusieurs algorithmes permettant de manipuler des polyèdres tropicaux. Ceux-ci correspondent aux travaux décrits dans § 6.2.1 . Ils permettent notamment de déterminer les sommets et rayons extrêmes d'un polyèdre tropical défini comme intersection de demi-espaces, ou inversement, de calculer une représentation externe à partir d'un ensemble de générateurs. Ces algorithmes sont implémentés la bibliothèque TPLib (voir § 5.3 ).

English version

X. Allamigeon, S. Gaubert, and E. Goubault, have developed in  [82] ,[57] algorithms allowing one to manipulate tropical polyhedra. They correspond to the contributions described in § 6.2.1 . In particular, they can be used to determine the vertices and extreme rays of a tropical polyhedron defined as the intersection of half-spaces, or inversely, to compute an external description from a set of generators. These algorithms are implemented in the library TPLib (see § 5.3 ).

Problèmes d'accessibilité dans les hypergraphes orientés et leur complexité/Reachability problems in directed hypergraphs and their complexity

Participant : Xavier Allamigeon.

Les hypergraphes orientés sont une généralisation des graphes orientés, dans lesquelles chaque arc relie un ensemble de sommets à un autre. Ils jouent un rôle important dans les travaux récents sur la convexité tropicale (voir § 6.2.1 ), puisqu'ils offrent une représentation naturelle des cônes définis sur le sous-semi-anneau booléen $𝔹=\{-\infty ,0\}$.

Dans un travail de X. Allamigeon [56] , on étudie la complexité de problèmes d'accessibilité sur les hypergraphes orientés. Nous introduisons un algorithme de complexité presque linéaire permettant de déterminer les composantes fortement connexes terminales (qui n'accèdent à aucune autre composante si ce n'est elles-mêmes) d'un hypergraphe.

Nous établissons également une borne inférieure sur-linéaire sur la taille de la réduction transitive de la relation d'accessibilité dans les hypergraphes. Cela indique que la relation d'accessibilité dans les hypergraphes orientés est combinatoirement plus complexe que celle des graphes orientés. Cela suggère aussi que des problèmes comme le calcul des composantes fortement connexes est plus difficile sur les hypergraphes que sur les graphes. Nous mettons d'ailleurs en évidence une réduction en temps linéaire du problème du calcul des ensembles minimaux dans une famille d'ensembles donnée, vers le problème du calcul de toutes les composantes fortement connexes d'un hypergraphe. Le problème du calcul des ensembles minimaux a été largement étudié dans la littérature  [163] , [183] , [182] , [164] , [165] , [166] , [118] , [88] , et aucune algorithme en temps linéaire n'est connu à ce jour.

English version

Directed hypergraphs are a generalization of directed graphs, in which the tail and the head of the arcs are sets of vertices. It appears that they play an important role in the recent works on tropical convexity (see § 6.2.1 ), since they offer a natural representation of cones defined over the boolean sub-semiring $𝔹=\{-\infty ,0\}$.

In a work of X. Allamigeon [56] , we study the complexity of reachability problems on directed hypergraphs. We introduce an almost linear-time algorithm allowing to determine the terminal strongly connected components (a component is said to be terminal when no other component is reachable from it).

We also establish a super-linear lower bound over the size of the transitive reduction of the reachability relation in directed hypergraphs. This indicates that the reachability relation is combinatorially more complex in directed hypergraphs than in directed graphs. This also suggests that reachability problems such as computing all strongly connected components are likely to be harder in hypergraphs than in graphs. Besides, we show that the minimal set problem can be reduced in linear time to the problem of computing all strongly connected components in hypergraphs. The former problem consists in finding all minimal sets among a given family of sets. It has been well studied in the literature  [163] , [183] , [182] , [164] , [165] , [166] , [118] , [88] , and no linear time algorithm is known.

Approximation max-plus de fonctions valeurs/Max-plus approximation of value functions

Participants : Stéphane Gaubert, Zheng Qu, Shanjian Tang [Fudan University, Shanghai] , William McEneaney [San Diego Univerisity] .

La thèse de Zheng Qu, démarrée en septembre 2010, supervisée par S. Gaubert et S. Tang, porte sur le développement de méthodes tropicales en programmation dynamique approchée.

Un problème de base consiste à approcher au mieux la fonction valeur d'un problème de contrôle ou de jeux par le supremum d'un petit nombre de fonctions choisies dans un dictionnaire fixé a priori. Ce problème est abordé dans [43] . À l'aide de résultats de Grüber portant sur l'approximation de corps convexes par des polytopes, on donne tout d'abord une borne montrant le caractère inévitable de la malédiction de la dimension, pour certaines méthodes de type base max-plus, lorsque la fonction valeur est $C^2$ et strictement convexe. Ce résultat montre que ces familles de méthodes sont asymptotiquement coûteuses lorsque la précision requise tends vers 0. Elles permettent cependant d'obtenir rapidement des approximations certifiées d'une précision donnée pas trop petite (dans ce cas, la malédiction de la dimension est absente). On s'intéresse ensuite à un problème algorithmique clé sous-jacent à ces méthodes, qui consiste à éliminer dynamiquement des fonctions redondantes intervenant dans la représentation. On démontre dans [43] que ce problème est équivalent à un problème géométrique de localisation, dans lequel la métrique est non symétrique (de type Bregman). Ceci a permis d'appliquer divers algorithmes de localisation, conduisant à une amélioraton de la méthode antérieure  [155] .

Un autre travail de Zheng Qu porte sur les équations de Riccati généralisées associées à des problèmes de contrôles stochastique avec critère quadratique, dans lesquels la dynamique comporte un terme bilinéaire en le contrôle et le bruit. Alors que le flot de l'équation de Riccati classique est contractant pour la métrique Riemanienne invariante, pour la métrique de Thompson, ainsi que pour toutes les métriques de Finsler invariantes sur le cône des matrices symmétriques positives, on montre ici que le flot de l'équation de Riccati généralisée en question est seulement contractant pour la métrique de Thompson (sous des hypothèses naturelles).

English version

The PhD work of Zheng Qu, which started in September 2010, and is supervised by S. Gaubert and S. Tang, aims in particular at developing tropical methods in approximate dynamic programming.

A basic problem consits in approximating the value function of an optimal control or game problem by a supremum of a small number of functions taken from a prescribed dictionnary. This problem is addressed in [43] . By applying results of Grüber concerning the approximation of convex bodies by polytopes, we give first a negative result, showing that the curse of dimensionality cannot be avoided by a family of max-plus basis methods, when the value function is $C^2$ and strictly convex. This result shows that this family of methods is asymptotically computationnaly expensive when the requested precision tends to 0. However, they can be used to obtain quickly (in a curse of dimensionality free way) certified approximations with a fixed (not too small) precision. Then, we addressed a key algorithmic subproblem, consisting in trimming dynamically the redundant functions in a max-plus representation. We showed in [43] that this problem is equivalent to a geometric facility location problem, with a non symmetric Bregman type metric. This allowed us to apply several facility location algorithms, leading to an improvement of the earlier method  [155] .

Another work of Zheng Qu deals with the generalized Riccati equations associated to stochastic optimal control problems with quadratic cost, in which the dynamics comprises a term which is bilinear in the control and in the noise. Whereas the flow of the standard Riccati equation is known to be a contraction for the invariant Riemannian metric, the Thompson metric, and more generally, for all invariant Finsler metrics on the cone of positive definite matrices, it is shown here that the flow of this generalized Riccati equation is only contracting with respect to Thompson metric (under natural assumptions).